home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 16 / CU Amiga Magazine's Super CD-ROM 16 (1997-10-16)(EMAP Images)(GB)[!][issue 1997-11].iso / CUCD / Graphics / Ghostscript / source / gxpath.c < prev    next >
C/C++ Source or Header  |  1997-04-29  |  17KB  |  553 lines
  1. /* Copyright (C) 1989, 1995, 1996, 1997 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* gxpath.c */
  20. /* Internal path construction routines for Ghostscript library */
  21. #include "gx.h"
  22. #include "gserrors.h"
  23. #include "gsstruct.h"
  24. #include "gxfixed.h"
  25. #include "gzpath.h"
  26.  
  27. /* These routines all assume that all points are */
  28. /* already in device coordinates, and in fixed representation. */
  29. /* As usual, they return either 0 or a (negative) error code. */
  30.  
  31. /* Forward references */
  32. private subpath *path_alloc_copy(P1(gx_path *));
  33. private int gx_path_new_subpath(P1(gx_path *));
  34. #ifdef DEBUG
  35. private void gx_print_segment(P1(const segment *));
  36. #  define trace_segment(msg, pseg)\
  37.      if ( gs_debug_c('P') ) dprintf(msg), gx_print_segment(pseg);
  38. #else
  39. #  define trace_segment(msg, pseg) DO_NOTHING
  40. #endif
  41.  
  42. /* Macro for checking a point against a preset bounding box. */
  43. #define outside_bbox(ppath, px, py)\
  44.  (px < ppath->bbox.p.x || px > ppath->bbox.q.x ||\
  45.   py < ppath->bbox.p.y || py > ppath->bbox.q.y)
  46. #define check_in_bbox(ppath, px, py)\
  47.   if ( outside_bbox(ppath, px, py) )\
  48.     return_error(gs_error_rangecheck)
  49.  
  50. /* Structure descriptors for paths and path segment types. */
  51. public_st_path();
  52. private_st_segment();
  53. private_st_line();
  54. private_st_line_close();
  55. private_st_curve();
  56. private_st_subpath();
  57.  
  58. /* ------ Initialize/free paths ------ */
  59.  
  60. /* Allocate and initialize a path. */
  61. gx_path *
  62. gx_path_alloc(gs_memory_t *mem, client_name_t cname)
  63. {    gx_path *ppath = gs_alloc_struct(mem, gx_path, &st_path, cname);
  64.     if ( ppath == 0 )
  65.       return 0;
  66.     gx_path_init(ppath, mem);
  67.     return ppath;
  68. }
  69.  
  70. /* Initialize a path */
  71. void
  72. gx_path_init(gx_path *ppath, gs_memory_t *mem)
  73. {    ppath->memory = mem;
  74.     gx_path_reset(ppath);
  75. }
  76. void
  77. gx_path_reset(gx_path *ppath)
  78. {    ppath->box_last = 0;
  79.     ppath->first_subpath = ppath->current_subpath = 0;
  80.     ppath->subpath_count = 0;
  81.     ppath->curve_count = 0;
  82.     path_update_newpath(ppath);
  83.     ppath->shares_segments = 0;
  84.     ppath->bbox_set = 0;
  85. }
  86.  
  87. /* Release the contents of a path.  We do this in reverse order */
  88. /* so as to maximize LIFO allocator behavior. */
  89. void
  90. gx_path_release(gx_path *ppath)
  91. {    segment *pseg;
  92.     if ( ppath->first_subpath == 0 ) return;    /* empty path */
  93.     if ( ppath->shares_segments ) return;    /* segments are shared */
  94.     pseg = (segment *)ppath->current_subpath->last;
  95.     while ( pseg )
  96.     {    segment *prev = pseg->prev;
  97.         trace_segment("[P]release", pseg);
  98.         gs_free_object(ppath->memory, pseg, "gx_path_release");
  99.         pseg = prev;
  100.     }
  101.     /* Clear pointers to make things clean for garbage collection. */
  102.     ppath->box_last = 0;
  103.     ppath->first_subpath = ppath->current_subpath = 0;
  104. }
  105.  
  106. /* Mark a path as shared */
  107. void
  108. gx_path_share(gx_path *ppath)
  109. {    if ( ppath->first_subpath ) ppath->shares_segments = 1;
  110. }
  111.  
  112. /* ------ Incremental path building ------ */
  113.  
  114. /* Macro for opening the current subpath. */
  115. /* ppath points to the path; psub has been set to ppath->current_subpath. */
  116. #define path_open()\
  117.     if ( !path_is_drawing(ppath) )\
  118.        {    int code;\
  119.         if ( !path_position_valid(ppath) )\
  120.           return_error(gs_error_nocurrentpoint);\
  121.         code = gx_path_new_subpath(ppath);\
  122.         if ( code < 0 ) return code;\
  123.         psub = ppath->current_subpath;\
  124.        }
  125.  
  126. /* Macros for allocating path segments. */
  127. /* Note that they assume that ppath points to the path, */
  128. /* and that psub points to the current subpath. */
  129. /* We have to split the macro into two because of limitations */
  130. /* on the size of a single statement (sigh). */
  131. #define path_unshare(ppath)\
  132.   if(ppath->shares_segments)\
  133.     if(!(psub = path_alloc_copy(ppath)))return_error(gs_error_VMerror)
  134. #define path_alloc_segment(pseg,ctype,pstype,stype,snotes,cname)\
  135.   path_unshare(ppath);\
  136.   if( !(pseg = gs_alloc_struct(ppath->memory, ctype, pstype, cname)) )\
  137.     return_error(gs_error_VMerror);\
  138.   pseg->type = stype, pseg->notes = snotes, pseg->next = 0
  139. #define path_alloc_link(pseg)\
  140.   { segment *prev = psub->last;\
  141.     prev->next = (segment *)pseg;\
  142.     pseg->prev = prev;\
  143.     psub->last = (segment *)pseg;\
  144.   }
  145.  
  146. /* Open a new subpath. */
  147. /* The client must invoke path_update_xxx. */
  148. private int
  149. gx_path_new_subpath(gx_path *ppath)
  150. {    subpath *psub = ppath->current_subpath;
  151.     subpath *spp;
  152.  
  153.     path_alloc_segment(spp, subpath, &st_subpath, s_start, sn_none,
  154.                "gx_path_new_subpath");
  155.     spp->last = (segment *)spp;
  156.     spp->curve_count = 0;
  157.     spp->is_closed = 0;
  158.     spp->pt = ppath->position;
  159.     if ( !psub )            /* first subpath */
  160.       { ppath->first_subpath = spp;
  161.         spp->prev = 0;
  162.       }
  163.     else
  164.       { segment *prev = psub->last;
  165.  
  166.         prev->next = (segment *)spp;
  167.         spp->prev = prev;
  168.       }
  169.     ppath->current_subpath = spp;
  170.     ppath->subpath_count++;
  171.     trace_segment("[P]", (const segment *)spp);
  172.     return 0;
  173. }
  174.  
  175. /* Add a point to the current path (moveto). */
  176. int
  177. gx_path_add_point(gx_path *ppath, fixed x, fixed y)
  178. {    if ( ppath->bbox_set )
  179.       check_in_bbox(ppath, x, y);
  180.     ppath->position.x = x;
  181.     ppath->position.y = y;
  182.     path_update_moveto(ppath);
  183.     return 0;
  184. }
  185.  
  186. /* Add a relative point to the current path (rmoveto). */
  187. int
  188. gx_path_add_relative_point(gx_path *ppath, fixed dx, fixed dy)
  189. {    if ( !path_position_in_range(ppath) )
  190.       return_error((path_position_valid(ppath) ? gs_error_limitcheck :
  191.             gs_error_nocurrentpoint));
  192.     { fixed nx = ppath->position.x + dx, ny = ppath->position.y + dy;
  193.       /* Check for overflow in addition. */
  194.       if ( ((nx ^ dx) < 0 && (ppath->position.x ^ dx) >= 0) ||
  195.            ((ny ^ dy) < 0 && (ppath->position.y ^ dy) >= 0)
  196.          )
  197.         return_error(gs_error_limitcheck);
  198.       if ( ppath->bbox_set )
  199.         check_in_bbox(ppath, nx, ny);
  200.       ppath->position.x = nx;
  201.       ppath->position.y = ny;
  202.     }
  203.     path_update_moveto(ppath);
  204.     return 0;
  205. }
  206.  
  207. /* Set the segment point and the current point in the path. */
  208. /* Assumes ppath points to the path. */
  209. #define path_set_point(pseg, fx, fy)\
  210.     (pseg)->pt.x = ppath->position.x = (fx),\
  211.     (pseg)->pt.y = ppath->position.y = (fy)
  212.  
  213. /* Add a line to the current path (lineto). */
  214. int
  215. gx_path_add_line_notes(gx_path *ppath, fixed x, fixed y, segment_notes notes)
  216. {    subpath *psub = ppath->current_subpath;
  217.     line_segment *lp;
  218.  
  219.     if ( ppath->bbox_set )
  220.       check_in_bbox(ppath, x, y);
  221.     path_open();
  222.     path_alloc_segment(lp, line_segment, &st_line, s_line, notes,
  223.                "gx_path_add_line");
  224.     path_alloc_link(lp);
  225.     path_set_point(lp, x, y);
  226.     path_update_draw(ppath);
  227.     trace_segment("[P]", (segment *)lp);
  228.     return 0;
  229. }
  230.  
  231. /* Add multiple lines to the current path. */
  232. /* Note that all lines have the same notes. */
  233. int
  234. gx_path_add_lines_notes(gx_path *ppath, const gs_fixed_point *ppts, int count,
  235.   segment_notes notes)
  236. {    subpath *psub = ppath->current_subpath;
  237.     segment *prev;
  238.     line_segment *lp = 0;
  239.     int i;
  240.     int code = 0;
  241.  
  242.     if ( count <= 0 )
  243.       return 0;
  244.     path_unshare(ppath);
  245.     path_open();
  246.     prev = psub->last;
  247.     /* We could do better than the following, but this is a start. */
  248.     /* Note that we don't make any attempt to undo partial additions */
  249.     /* if we fail partway through; this is equivalent to what would */
  250.     /* happen with multiple calls on gx_path_add_line. */
  251.     for ( i = 0; i < count; i++ )
  252.       {    fixed x = ppts[i].x;
  253.         fixed y = ppts[i].y;
  254.         line_segment *next;
  255.         if ( ppath->bbox_set && outside_bbox(ppath, x, y) )
  256.           {    code = gs_note_error(gs_error_rangecheck);
  257.             break;
  258.           }
  259.         if ( !(next = gs_alloc_struct(ppath->memory, line_segment,
  260.                           &st_line, "gx_path_add_lines"))
  261.            )
  262.           {    code = gs_note_error(gs_error_VMerror);
  263.             break;
  264.           }
  265.         lp = next;
  266.         lp->type = s_line;
  267.         lp->notes = notes;
  268.         prev->next = (segment *)lp;
  269.         lp->prev = prev;
  270.         lp->pt.x = x;
  271.         lp->pt.y = y;
  272.         prev = (segment *)lp;
  273.         trace_segment("[P]", (segment *)lp);
  274.       }
  275.     if ( lp != 0 )
  276.       ppath->position.x = lp->pt.x,
  277.       ppath->position.y = lp->pt.y,
  278.       psub->last = (segment *)lp,
  279.       lp->next = 0,
  280.       path_update_draw(ppath);
  281.     return code;
  282. }
  283.  
  284. /* Add a rectangle to the current path. */
  285. /* This is a special case of adding a closed polygon. */
  286. int
  287. gx_path_add_rectangle(gx_path *ppath, fixed x0, fixed y0, fixed x1, fixed y1)
  288. {    gs_fixed_point pts[3];
  289.     int code;
  290.  
  291.     pts[0].x = x0;
  292.     pts[1].x = pts[2].x = x1;
  293.     pts[2].y = y0;
  294.     pts[0].y = pts[1].y = y1;
  295.     if ( (code = gx_path_add_point(ppath, x0, y0)) < 0 ||
  296.          (code = gx_path_add_lines(ppath, pts, 3)) < 0 ||
  297.          (code = gx_path_close_subpath(ppath)) < 0
  298.        )
  299.       return code;
  300.     return 0;
  301. }
  302.  
  303. /* Add a curve to the current path (curveto). */
  304. int
  305. gx_path_add_curve_notes(gx_path *ppath,
  306.   fixed x1, fixed y1, fixed x2, fixed y2, fixed x3, fixed y3,
  307.   segment_notes notes)
  308. {    subpath *psub = ppath->current_subpath;
  309.     curve_segment *lp;
  310.  
  311.     if ( ppath->bbox_set )
  312.     {    check_in_bbox(ppath, x1, y1);
  313.         check_in_bbox(ppath, x2, y2);
  314.         check_in_bbox(ppath, x3, y3);
  315.     }
  316.     path_open();
  317.     path_alloc_segment(lp, curve_segment, &st_curve, s_curve, notes,
  318.                "gx_path_add_curve");
  319.     path_alloc_link(lp);
  320.     lp->p1.x = x1;
  321.     lp->p1.y = y1;
  322.     lp->p2.x = x2;
  323.     lp->p2.y = y2;
  324.     path_set_point(lp, x3, y3);
  325.     psub->curve_count++;
  326.     ppath->curve_count++;
  327.     path_update_draw(ppath);
  328.     trace_segment("[P]", (segment *)lp);
  329.     return 0;
  330. }
  331.  
  332. /*
  333.  * Add an approximation of an arc to the current path.
  334.  * The current point of the path is the initial point of the arc;
  335.  * parameters are the final point of the arc
  336.  * and the point at which the extended tangents meet.
  337.  * We require that the arc be less than a semicircle.
  338.  * The arc may go either clockwise or counterclockwise.
  339.  * The approximation is a very simple one: a single curve
  340.  * whose other two control points are a fraction F of the way
  341.  * to the intersection of the tangents, where
  342.  *    F = (4/3)(1 / (1 + sqrt(1+(d/r)^2)))
  343.  * where r is the radius and d is the distance from either tangent
  344.  * point to the intersection of the tangents.  This produces
  345.  * a curve whose center point, as well as its ends, lies on
  346.  * the desired arc.
  347.  *
  348.  * Because F has to be computed in user space, we let the client
  349.  * compute it and pass it in as an argument.
  350.  */
  351. int
  352. gx_path_add_partial_arc_notes(gx_path *ppath,
  353.   fixed x3, fixed y3, fixed xt, fixed yt, floatp fraction, segment_notes notes)
  354. {    fixed x0 = ppath->position.x, y0 = ppath->position.y;
  355.     return gx_path_add_curve_notes(ppath,
  356.             x0 + (fixed)((xt - x0) * fraction),
  357.             y0 + (fixed)((yt - y0) * fraction),
  358.             x3 + (fixed)((xt - x3) * fraction),
  359.             y3 + (fixed)((yt - y3) * fraction),
  360.             x3, y3, notes | sn_from_arc);
  361. }
  362.  
  363. /* Append a path to another path, and reset the first path. */
  364. /* Currently this is only used to append a path to its parent */
  365. /* (the path in the previous graphics context). */
  366. int
  367. gx_path_add_path(gx_path *ppath, gx_path *ppfrom)
  368. {    subpath *psub;
  369.     path_unshare(ppfrom);
  370.     path_unshare(ppath);
  371.     if ( ppfrom->first_subpath )    /* i.e. ppfrom not empty */
  372.        {    if ( ppath->first_subpath )    /* i.e. ppath not empty */
  373.            {    subpath *psub = ppath->current_subpath;
  374.             segment *pseg = psub->last;
  375.             subpath *pfsub = ppfrom->first_subpath;
  376.             pseg->next = (segment *)pfsub;
  377.             pfsub->prev = pseg;
  378.            }
  379.         else
  380.             ppath->first_subpath = ppfrom->first_subpath;
  381.         ppath->current_subpath = ppfrom->current_subpath;
  382.         ppath->subpath_count += ppfrom->subpath_count;
  383.         ppath->curve_count += ppfrom->curve_count;
  384.        }
  385.     /* Transfer the remaining state. */
  386.     ppath->position = ppfrom->position;
  387.     ppath->outside_position = ppfrom->outside_position;
  388.     ppath->state_flags = ppfrom->state_flags;
  389.     gx_path_reset(ppfrom);        /* reset the source path */
  390.     return 0;
  391. }
  392.  
  393. /* Add a path or its bounding box to the enclosing path, */
  394. /* and reset the first path.  Only used for implementing charpath and its */
  395. /* relatives. */
  396. int
  397. gx_path_add_char_path(gx_path *to_path, gx_path *from_path,
  398.   gs_char_path_mode mode)
  399. {    switch ( mode )
  400.       {
  401.       default:            /* shouldn't happen! */
  402.         gx_path_reset(from_path);
  403.         return 0;
  404.       case cpm_true_charpath:
  405.       case cpm_false_charpath:
  406.         return gx_path_add_path(to_path, from_path);
  407.       case cpm_true_charboxpath:
  408.         { gs_fixed_rect bbox;
  409.           gx_path_bbox(from_path, &bbox);
  410.           return gx_path_add_rectangle(to_path, bbox.p.x, bbox.p.y,
  411.                        bbox.q.x, bbox.q.y);
  412.         }
  413.       case cpm_false_charboxpath:
  414.         { gs_fixed_rect bbox;
  415.           int code;
  416.           gx_path_bbox(from_path, &bbox);
  417.           return
  418.         ((code = gx_path_add_point(to_path, bbox.p.x, bbox.p.y)) < 0 ?
  419.          code : gx_path_add_line(to_path, bbox.q.x, bbox.q.y));
  420.         }
  421.       }
  422. }
  423.  
  424. /* Close the current subpath. */
  425. int
  426. gx_path_close_subpath_notes(gx_path *ppath, segment_notes notes)
  427. {    subpath *psub = ppath->current_subpath;
  428.     line_close_segment *lp;
  429.     int code;
  430.  
  431.     if ( !path_subpath_open(ppath) )
  432.       return 0;
  433.     if ( path_last_is_moveto(ppath) )
  434.       { /* The last operation was a moveto: create a subpath. */
  435.         code = gx_path_new_subpath(ppath);
  436.         if ( code < 0 )
  437.           return code;
  438.         psub = ppath->current_subpath;
  439.       }
  440.     path_alloc_segment(lp, line_close_segment, &st_line_close,
  441.                s_line_close, notes, "gx_path_close_subpath");
  442.     path_alloc_link(lp);
  443.     path_set_point(lp, psub->pt.x, psub->pt.y);
  444.     lp->sub = psub;
  445.     psub->is_closed = 1;
  446.     path_update_closepath(ppath);
  447.     trace_segment("[P]", (segment *)lp);
  448.     return 0;
  449. }
  450.  
  451. /* Remove the last line from the current subpath, and then close it. */
  452. /* The Type 1 font hinting routines use this if a path ends with */
  453. /* a line to the start followed by a closepath. */
  454. int
  455. gx_path_pop_close_notes(gx_path *ppath, segment_notes notes)
  456. {    subpath *psub = ppath->current_subpath;
  457.     segment *pseg;
  458.     segment *prev;
  459.  
  460.     if ( psub == 0 || (pseg = psub->last) == 0 ||
  461.          pseg->type != s_line
  462.        )
  463.       return_error(gs_error_unknownerror);
  464.     prev = pseg->prev;
  465.     prev->next = 0;
  466.     psub->last = prev;
  467.     gs_free_object(ppath->memory, pseg, "gx_path_pop_close_subpath");
  468.     return gx_path_close_subpath_notes(ppath, notes);
  469. }
  470.  
  471. /* ------ Internal routines ------ */
  472.  
  473. /* Copy the current path, because it was shared. */
  474. /* Return a pointer to the current subpath, or 0. */
  475. private subpath *
  476. path_alloc_copy(gx_path *ppath)
  477. {    gx_path path_new;
  478.     int code;
  479.     code = gx_path_copy(ppath, &path_new, 1);
  480.     if ( code < 0 ) return 0;
  481.     *ppath = path_new;
  482.     ppath->shares_segments = 0;
  483.     return ppath->current_subpath;
  484. }
  485.  
  486. /* ------ Debugging printout ------ */
  487.  
  488. #ifdef DEBUG
  489.  
  490. /* Print out a path with a label */
  491. void
  492. gx_dump_path(const gx_path *ppath, const char *tag)
  493. {    dprintf2("[P]Path 0x%lx %s:\n", (ulong)ppath, tag);
  494.     gx_path_print(ppath);
  495. }
  496.  
  497. /* Print a path */
  498. void
  499. gx_path_print(const gx_path *ppath)
  500. {    const segment *pseg = (const segment *)ppath->first_subpath;
  501.     dprintf5("   state_flags=%d subpaths=%d, curves=%d, point=(%f,%f)\n",
  502.          ppath->state_flags, ppath->subpath_count, ppath->curve_count,
  503.          fixed2float(ppath->position.x),
  504.          fixed2float(ppath->position.y));
  505.     dprintf5("   box=(%f,%f),(%f,%f) last=0x%lx\n",
  506.          fixed2float(ppath->bbox.p.x), fixed2float(ppath->bbox.p.y),
  507.          fixed2float(ppath->bbox.q.x), fixed2float(ppath->bbox.q.y),
  508.          (ulong)ppath->box_last);
  509.     while ( pseg )
  510.        {    gx_print_segment(pseg);
  511.         pseg = pseg->next;
  512.        }
  513. }
  514. private void
  515. gx_print_segment(const segment *pseg)
  516. {    double px = fixed2float(pseg->pt.x);
  517.     double py = fixed2float(pseg->pt.y);
  518.     char out[80];
  519.  
  520.     sprintf(out, "   0x%lx<0x%lx,0x%lx>:%u",
  521.         (ulong)pseg, (ulong)pseg->prev, (ulong)pseg->next,
  522.         pseg->notes);
  523.     switch ( pseg->type )
  524.       {
  525.       case s_start:
  526. #define psub ((const subpath *)pseg)
  527.         dprintf5("%s: %6g %6g moveto\t%% #curves=%d last=0x%lx\n",
  528.              out, px, py, psub->curve_count, (ulong)psub->last);
  529. #undef psub
  530.         break;
  531.       case s_curve:
  532. #define pcur ((const curve_segment *)pseg)
  533.         dprintf7("%s: %g %g %g %g %g %g curveto\n",
  534.              out, fixed2float(pcur->p1.x), fixed2float(pcur->p1.y),
  535.              fixed2float(pcur->p2.x), fixed2float(pcur->p2.y), px, py);
  536. #undef pcur
  537.         break;
  538.       case s_line:
  539.         dprintf3("%s: %6g %6g lineto\n", out, px, py);
  540.         break;
  541.       case s_line_close:
  542. #define plc ((const line_close_segment *)pseg)
  543.         dprintf4("%s: closepath\t%% %g %g 0x%lx\n",
  544.              out, px, py, (ulong)(plc->sub));
  545. #undef plc
  546.         break;
  547.       default:
  548.         dprintf4("%s: %g %g <type 0x%x>\n", out, px, py, pseg->type);
  549.       }
  550. }
  551.  
  552. #endif                    /* DEBUG */
  553.